// 给定两个二进制字符串，返回他们的和（用二进制表示）。

// 输入为非空字符串且只包含数字 1 和 0。

// 示例 1:

// 输入: a = "11", b = "1"
// 输出: "100"
// 示例 2:

// 输入: a = "1010", b = "1011"
// 输出: "10101"

#include <string>
#include <algorithm>

using std::max;
using std::string;
using std::to_string;

class Solution1 {
public:
    string addBinary(string a, string b) {
        string res{};
        int na = a.size();
        int nb = b.size();
        int n = max(na, nb);
        bool carry = false;
        // 把两个字符串变得一样长，方便接下来操作
        if (na > nb) {
            for (int i{0}; i < na - nb; ++i)
                b.insert(b.begin(), '0');
        } else if (na <nb) {
            for (int i{0}; i < nb - na; ++i)
                a.insert(a.begin(), '0');
        }
        for (int i{n-1}; i >= 0; --i) {
            int tmp{0}; // 当前和
            if (carry) tmp = (a[i] - '0') + (b[i] - '0') + 1;
            else tmp = (a[i] - '0') + (b[i] - '0');
            if (tmp == 0) {
                res.insert(res.begin(), '0');
                carry = false;
            } else if (tmp == 1) {
                res.insert(res.begin(), '1');
                carry = false;
            } else if (tmp == 2) {
                res.insert(res.begin(), '0');
                carry = true;
            } else if (tmp == 3) {
                res.insert(res.begin(), '1');
                carry = true;
            }
        }
        if (carry) res.insert(res.begin(), '1');
        return res;
    }
};

class Solution {
public:
    string addBinary(string a, string b) {
        string res{};
        int m = a.size() - 1;
        int n = b.size() - 1;
        int carry{0};
        while (m >= 0 || n >= 0) {
            int p = (m >= 0 ? a[m--] - '0' : 0);
            int q = (n >= 0 ? b[n--] - '0' : 0);
            int sum = p + q + carry;
            res = to_string(sum % 2) +res;
            carry = sum / 2;
        }
        return carry == 1 ? "1" + res : res;
    }
};

class Solution {
public:
    string addBinary(string a, string b) {
        string res{};
        int m = a.size() - 1;
        int n = b.size() - 1;
        int carry{0};
        int sum{0};
        while (m >= 0 || n >= 0) {
            int p = (m >= 0 ? a[m] - '0' : 0);
            int q = (n >= 0 ? b[n] - '0' : 0);
            sum = p + q + carry;
            carry = sum / 2;
            res = to_string(sum % 2) + res;
            --m;
            --n;
        }
        if (carry == 1) res = "1" + res;
        return res;
    }
};

// 自己能写出来的版本
class Solution {
public:
    string addBinary(string a, string b) {
        string res{};
        int m = a.size() - 1;
        int n = b.size() - 1;
        int jinwei{0};
        int sum{0};
        while (m >= 0 && n >= 0) {
            sum = (a[m] - '0') + (b[n] - '0') + jinwei;
            jinwei = sum / 2;
            res = to_string(sum % 2) + res;
            --m;
            --n;
        }
        while (m >= 0) {
            sum = (a[m] - '0') + jinwei;
            jinwei = sum / 2;
            res = to_string(sum % 2) + res;
            --m;
        }
        while (n >= 0) {
            sum = (b[n] - '0') + jinwei;
            jinwei = sum / 2;
            res = to_string(sum % 2) + res;
            --n;
        }
        if (jinwei == 1) res = to_string(1) + res;
        return res;
    }
};